let ROW = 5;
let COL = 4;

function solve(bs) {
	let queue = [];
	let set = new Set();

	let arr = bsToArray(bs);
	if (arr[3][1] == block_number["B"] && arr[4][2] == block_number["B"]) {
		return [];
	}

	let str = arrToString(arr);

	queue.push({
		bs: bs,
		idx: -1,
		lb: -1,
		ld: null
	});
	set.add(str);

	let index = 0;

	while (index < queue.length) {
		let nbs = queue[index].bs;

		let narr = bsToArray(nbs);

		if (narr[3][1] == block_number["B"] && narr[4][2] == block_number["B"]) {
			break;
		}

		for (let i = 0; i < nbs.length; i++) {
			let b = nbs[i];
			if (bCanGoLeft(b, narr)) {
				let new_bs = bsClone(nbs);
				new_bs[i].y -= 1;
				let new_arr = bsToArray(new_bs);
				let new_str = arrToString(new_arr);
				if (!set.has(new_str)) {
					set.add(new_str);
					queue.push({
						bs: new_bs,
						idx: index,
						lb: i,
						ld: "Left"
					});
				}
			}
			if (bCanGoRight(b, narr)) {
				let new_bs = bsClone(nbs);
				new_bs[i].y += 1;
				let new_arr = bsToArray(new_bs);
				let new_str = arrToString(new_arr);
				if (!set.has(new_str)) {
					set.add(new_str);
					queue.push({
						bs: new_bs,
						idx: index,
						lb: i,
						ld: "Right"
					});
				}
			}
			if (bCanGoUp(b, narr)) {
				let new_bs = bsClone(nbs);
				new_bs[i].x -= 1;
				let new_arr = bsToArray(new_bs);
				let new_str = arrToString(new_arr);
				if (!set.has(new_str)) {
					set.add(new_str);
					queue.push({
						bs: new_bs,
						idx: index,
						lb: i,
						ld: "Up"
					});
				}
			}
			if (bCanGoDown(b, narr)) {
				let new_bs = bsClone(nbs);
				new_bs[i].x += 1;

				let new_arr = bsToArray(new_bs);
				let new_str = arrToString(new_arr);
				if (!set.has(new_str)) {
					set.add(new_str);
					queue.push({
						bs: new_bs,
						idx: index,
						lb: i,
						ld: "Down"
					});
				}
			}
		}

		index++;
	}

	if (index < queue.length) {
		let res = [];
		while (index != -1) {
			res.unshift(queue[index]);
			index = queue[index].idx;
		}
		return res;
	} else {
		return null;
	}
}

function bsToArray(bs) {
	let arr = [];
	for (let i = 0; i < ROW; i++) {
		arr.push([]);
		for (let j = 0; j < COL; j++) {
			arr[i].push(0);
		}
	}
	bs.forEach((b, _) => {
		for (let i = b.x; i < b.x + b.h; i++) {
			for (let j = b.y; j < b.y + b.w; j++) {
				arr[i][j] = block_number[b.bt];
			}
		}
	});
	return arr;
}

function arrToString(arr) {
	let str = "";
	for (let i = 0; i < ROW; i++) {
		for (let j = 0; j < COL; j++) {
			str += arr[i][j];
		}
	}
	return str;
}

function bsClone(bs) {
	let res = [];
	for (let i = 0; i < bs.length; i++) {
		res.push({
			bt: bs[i].bt,
			x: bs[i].x,
			y: bs[i].y,
			w: bs[i].w,
			h: bs[i].h
		});
	}
	return res;
}

function bCanGoLeft(b, arr) {
	if (b.y - 1 < 0) {
		return false;
	}
	for (let i = b.x, j = b.y - 1; i < b.x + b.h; i++) {
		if (arr[i][j] != 0) {
			return false;
		}
	}
	return true;
}

function bCanGoRight(b, arr) {
	if (b.y + b.w >= COL) {
		return false;
	}
	for (let i = b.x, j = b.y + b.w; i < b.x + b.h; i++) {
		if (arr[i][j] != 0) {
			return false;
		}
	}
	return true;
}

function bCanGoUp(b, arr) {
	if (b.x - 1 < 0) {
		return false;
	}
	for (let i = b.x - 1, j = b.y; j < b.y + b.w; j++) {
		if (arr[i][j] != 0) {
			return false;
		}
	}
	return true;
}

function bCanGoDown(b, arr) {
	if (b.x + b.h >= ROW) {
		return false;
	}
	for (let i = b.x + b.h, j = b.y; j < b.y + b.w; j++) {
		if (arr[i][j] != 0) {
			return false;
		}
	}
	return true;
}